package org.example.chap03;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode-cn.com/problems/two-sum/description/
 */
public class Twosum {
    public static void main(String[] args) {
        int[] nums = {2,7,11,15};
        int target = 9;

        int[] result = solution2(nums,target);
        if(result == null){
            System.out.println("没有匹配的");
        }
        for (int i : result) {
            System.out.println(i);
        }

    }

    /**
     * 暴力算法 时间复杂度 O(N^2)
     * @param nums
     * @param target
     * @return
     */
    public static int[] solution1(int[] nums, int target){
        int len = nums.length;

        for (int i = 0; i < len; i++) {
            for (int j = i+1; j < len; j++) {
                if(nums[i]+nums[j] == target){
                    return new int[]{i,j};
                }
            }
        }
        return new int[0];
    }

    /**
     * 时间复杂度O（N）
     * @param nums 2,7,11,15
     * @param target
     * @return
     */
    public static int[] solution2(int[] nums,int target){
       int len = nums.length;
       Map<Integer,Integer> map = new HashMap<Integer,Integer>();
       for (int i = 0; i < len; i++) {
           if(map.containsKey(target - nums[i])){
               return new int[]{map.get(target - nums[i]),i};
           }
           map.put(nums[i],i);
       }
       return null;
    }
}
